#include <malloc.h>
#include <stdio.h>

typedef int ElemType;
typedef struct LNode {
    ElemType data;
    struct LNode *next; // 指向后继结点
} LinkNode;             // 声明单链表结点类型

void DispList(LinkNode *L) {
    if (L->next == NULL) {
        printf("NULL\n");
        return;
    }
    for (LinkNode *p = L->next; p != NULL; p = p->next) {
        printf("%d", p->data);
        if (p->next != NULL) {
            printf(" ");
        }
    }
    printf("\n");
}

// 已知两个非降序链表序列S1与S2，求S1与S2的交集新链表S3。
void Join(LinkNode* s1, LinkNode* s2, LinkNode *&s3) {
    LinkNode *p1 = s1->next, *p2 = s2->next, *r, *t;
    s3 = (LinkNode *)malloc(sizeof(LinkNode));
    s3->next = NULL;
    r = s3;
    while (p1 != NULL && p2 != NULL) {
        if (p1->data < p2->data) {
            p1 = p1->next;
        } else if (p1->data > p2->data) {
            p2 = p2->next;
        } else {
            t = (LinkNode *)malloc(sizeof(LinkNode));
            t->data = p1->data;
            r->next = t;
            r = t;
            p1 = p1->next;
            p2 = p2->next;
        }
    }
    r->next = NULL;
}

void input(LinkNode *&L) {
    LinkNode *s, *r;
    L = (LinkNode *)malloc(sizeof(LinkNode)); // 创建头结点
    L->next = NULL;
    r = L; // r始终指向终端结点,开始时指向头结点
    for (;;) {
        int x;
        scanf("%d", &x);
        if (x == -1) {
            break;
        }
        s = (LinkNode *)malloc(sizeof(LinkNode)); // 创建新结点s
        s->data = x;
        r->next = s; // 将结点s插入结点r之后
        r = s;
    }
    r->next = NULL; // 终端结点next域置为NULL
}

int main() {
    LinkNode *s1, *s2, *s3;
    input(s1);
    input(s2);
    Join(s1, s2, s3);
    DispList(s3);
    return 0;
}
